class Solution:
    def canCross(self, stones) -> bool:
        if len(stones) == 1:
            return True
        dp = [set() for _ in range(len(stones))]
        if stones[1]!=1:
            return False
        elif len(stones) == 2:
            return True
        dp[1].add(1)
        hash1 = {}
        for i in range(len(stones)):
            hash1[stones[i]] = i
        for i in range(1, len(stones)-1):
            for step in dp[i]:
                for newStep in [step + 1, step, step - 1]:
                    if newStep > 0 and stones[i] + newStep in hash1:
                        if hash1[stones[i] + newStep] == len(stones)-1:
                            # print(dp)
                            return True
                        dp[hash1[stones[i] + newStep]].add(newStep)

        # print(dp)
        return False


if __name__ == '__main__':
    so = Solution()
    num = [0,1,2,3,4,8,9,11]
    r = so.canCross(num)
    print(r)
